/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/majority-number-iii
   @Language: C++
   @Datetime: 16-02-09 05:59
   */

class Solution {
public:
	/**
	 * @param nums: A list of integers
	 * @param k: As described
	 * @return: The majority number
	 */
	/** Tips: The majority number occurs more than n/k times
	 *        and only have one majority number in nums
	 *
	 * we can use HashMap (c++ std called unordered_map) to store 
	 * the candidates of majority numbers. when the count of candidates
	 * reach to k, decrease their occur times and erase zero occurance number
	 * at last, the HashMap contains <= k candiates.
	 *
	 * then count the candidates' occurances, and find which occurs 
	 * more than n/k times.
	 * */
	int majorityNumber(vector<int> nums, int k) {
		// write your code here
		unordered_map<int,int> cans;
		unordered_map<int,int>::iterator it;
		for(int i=nums.size(); i--;){
			++cans[nums[i]];
			if (cans.size() < k) continue;
			// erase k elements each time
			for (it=cans.begin(); it!=cans.end();){
				if (--(it->second)) ++it;
				else cans.erase(it++);
			}
		}
		// reset count for candidates
		for(it=cans.begin(); it!=cans.end(); (it++)->second=0);
		// count each candidate elements occur times
		for(int i=nums.size(); i--;){
			it = cans.find(nums[i]);
			if (it != cans.end()) ++(it->second);
		}
		// find candidate element who occurs > n/k times
		for(it=cans.begin(); it!=cans.end(); ++it)
			if (it->second > 1.0*nums.size()/k) return it->first;
		return -1;
	}
};
